package com.kehao.newcoder;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class NC91Solution {
    public int[] LIS(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] dp = new int[arr.length];
        dp[0] = 1;
        int maxDpIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = 1;
            int maxDp = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && maxDp < dp[j]) {
                    maxDp = dp[j];
                }
            }
            int minASCII = 10;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && maxDp == dp[j] && minASCII>dp[j]) {
                    map.put(i,j);
                    dp[i] = dp[j]+1;
                    if(dp[i]>dp[maxDpIndex]){
                        maxDpIndex = i;
                    }else if(dp[i]==dp[maxDpIndex]&&arr[i]<arr[maxDpIndex]){
                        maxDpIndex = i;
                    }
                }
            }
        }
        int[] result = new int[dp[maxDpIndex]];
        int index = result.length;
        while (index > 0) {
            result[--index] = arr[maxDpIndex];
            if (map.containsKey(maxDpIndex)) {
                maxDpIndex = map.get(maxDpIndex);
            }
        }
        return result;
    }
    @Test
    public void test01 () {
        int[] arr = new int[]{2,1,5,3,6,4,8,9,7};
        int[] result = LIS(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
}